package ADD_project;

import java.util.Scanner;

public class MaximumPathSum {
    public static void main(String[] args) {
        System.out.println("请输入行数：");
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        System.out.println("请输入数据：");
        int[][] triangle = new int[n][n];

        // 输入数学三角形
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                triangle[i][j] = scanner.nextInt();
            }
        }

        int[][] dp = new int[n][n];
        // 初始化最后一行
        for (int j = 0; j < n; j++) {
            dp[n-1][j] = triangle[n-1][j];
        }

        // 自底向上计算最大路径和
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = Math.max(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j];
            }
        }
        //取到路径和的最大值
        int maxPathSum = dp[0][0];
        System.out.println("The maximum path sum is " + maxPathSum);
    }
}
